package william.backtracing;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @author ZhangShenao
 * @date 2024/4/4
 * @description <a href="https://leetcode.cn/problems/combinations/description/">...</a>
 */
public class Leetcode77_组合 {
    /**
     * 保存最终结果
     */
    private List<List<Integer>> result = new ArrayList<>();

    /**
     * 采用递归+回溯实现
     * 本质上就是求C(n,k)
     * 递推公式: 针对当前数字start,先将start放入组合,然后再从start+1开始找到剩余的k-1个数字
     * 使用剪枝进行优化
     */
    public List<List<Integer>> combine(int n, int k) {
        //边界条件校验
        if (n <= 0 || k <= 0 || k > n) {
            return Collections.emptyList();
        }

        //调用递归处理
        backTracing(n, k, 1, new LinkedList<>());

        //返回结果
        return result;
    }

    /**
     * 递归+回溯处理
     * 从start开始,寻找C(n,k),并将排列结果保存在prefix中
     */
    private void backTracing(int n, int k, int start, LinkedList<Integer> prefix) {
        //递归终止条件:找到了一组组合
        if (prefix.size() == k) {
            result.add(new ArrayList<>(prefix));
            return;
        }

        //递归+回溯处理
        //剪枝优化:组合剩余的元素数量=k-prefix.size(),需要保证[i,n]范围内至少还有k-prefix.size()个数字
        for (int i = start; i <= (n - (k - prefix.size() - 1)); i++) {
            //首先找到start,然后继续在start后面寻找组合
            prefix.addLast(i);
            backTracing(n, k, i + 1, prefix);

            //回溯:将i从prefix中移除
            prefix.removeLast();

        }
    }
}
